Read the original article here.

---

Explicitly Parallel Instruction Computing (EPIC): A Visionary but Underrealized Approach to Parallel Processing

In the relentless pursuit of faster and more efficient computing, innovation often pushes the boundaries of conventional wisdom. Explicitly Parallel Instruction Computing (EPIC) stands as a compelling example of such an innovation – a paradigm envisioned to revolutionize microprocessor design by shifting the complexities of parallel instruction execution from hardware to software. Coined in 1997 by the HP-Intel alliance, EPIC, also known as Independence architectures, aimed to achieve performance scaling without relying solely on increasing clock frequencies, a path that was becoming increasingly power-hungry and complex. While EPIC served as the foundation for Intel's Itanium architecture, its broader impact on mainstream computing remained limited, positioning it as a fascinating, yet somewhat "lost," innovation in the history of computer architecture.

Roots in Very Long Instruction Word (VLIW) Architecture

To understand EPIC, it's crucial to trace its origins back to Very Long Instruction Word (VLIW) architectures. By the late 1980s, researchers at HP recognized that Reduced Instruction Set Computer (RISC) architectures, then the dominant paradigm, were approaching a performance ceiling of one instruction per cycle. This realization sparked investigations into new architectural approaches, leading to the conceptualization of EPIC, firmly rooted in the principles of VLIW.

Very Long Instruction Word (VLIW): A computer architecture that packs multiple independent instructions into a single "very long instruction word." These instructions are designed to be executed in parallel by multiple execution units within the processor simultaneously. The key characteristic of VLIW is that the compiler, rather than the hardware, is responsible for scheduling these instructions to ensure they can be executed in parallel without conflicts.

In essence, VLIW sought to exploit Instruction-Level Parallelism (ILP) by explicitly encoding multiple operations within each instruction. Imagine a chef preparing a complex dish. In a traditional instruction set, each step (chop vegetables, boil water, sauté onions) would be a separate instruction executed sequentially. In a VLIW approach, the recipe might be structured as a single instruction that says "simultaneously chop vegetables, boil water, and sauté onions" – provided the kitchen has enough chefs and equipment to perform these tasks in parallel.

The core idea behind VLIW was to move the burden of instruction scheduling from the CPU hardware to the compiler. Compilers, with their ability to analyze code statically (before execution), could identify opportunities for parallel execution and arrange instructions accordingly. This offered several potential advantages:

• Simplified Hardware: By offloading scheduling to the compiler, the CPU hardware could be significantly simplified. Complex circuitry needed for dynamic instruction scheduling in superscalar processors could be eliminated.
• Increased Execution Resources: The freed-up hardware space and power could be redirected towards adding more execution units (like ALUs, FPUs, etc.), further enhancing parallel processing capabilities.
• Exploiting Instruction-Level Parallelism (ILP): VLIW aimed to maximize ILP by enabling the compiler to meticulously analyze code and uncover hidden opportunities for parallel execution that might be missed by hardware-based dynamic scheduling.

However, early VLIW designs encountered significant challenges that hindered their widespread adoption. The Wikipedia article points out two critical shortcomings:

1. Backward Incompatibility: VLIW instruction sets were inherently tied to specific hardware implementations. If a new processor design incorporated more execution units to handle wider VLIW instructions, the instruction set would become incompatible with older, narrower implementations. This meant software compiled for older VLIW processors would not run on newer ones, creating significant software compatibility issues. Think of it like changing the recipe format every time you get a bigger kitchen – all your old recipes become unusable!
2. Non-Deterministic Memory Latency: Memory access times, particularly involving caches and DRAM, are not always predictable. Cache hits are fast, while cache misses can lead to significantly longer delays as data needs to be fetched from main memory. This non-deterministic latency made it extremely difficult for compilers to statically schedule load instructions effectively. Imagine trying to plan the cooking perfectly when you don't know exactly how long it will take to retrieve ingredients from the pantry – sometimes they are right there, sometimes you have to go to the basement!

These limitations prevented early forms of VLIW from becoming a mainstream architecture. EPIC emerged as an evolution of VLIW, aiming to address these shortcomings while retaining the core benefits of compiler-directed parallelism.

Moving Beyond VLIW: EPIC's Innovations

Explicitly Parallel Instruction Computing (EPIC) was designed to overcome the limitations of traditional VLIW architectures while preserving its fundamental principle of compiler-driven parallelism. EPIC introduced several key features to enhance flexibility, efficiency, and scalability.

Bundles and Stop Bits: Addressing Backward Compatibility

EPIC introduced the concept of "bundles" to manage groups of instructions.

Bundle (in EPIC): A group of multiple instructions that are issued and potentially executed in parallel. In EPIC, instructions are not issued individually but in bundles, controlled by the compiler.

Instead of a single monolithic VLIW instruction, EPIC organized instructions into bundles. Each bundle contained a set of instructions intended for parallel execution. Crucially, each bundle also included a "stop bit."

Stop Bit (in EPIC Bundles): A bit within an EPIC instruction bundle that indicates whether the instructions in the current bundle are dependent on the instructions in the subsequent bundle. This bit signals to the hardware whether it can proceed to issue the next bundle immediately or if it needs to wait for the current bundle to complete due to data or control dependencies.

The stop bit was the key to addressing backward compatibility. Compilers were responsible for setting these stop bits based on data dependencies between bundles. This allowed future EPIC implementations to issue multiple bundles in parallel if they had sufficient hardware resources, while still maintaining compatibility with older implementations that might only issue one bundle at a time. The hardware would simply look at the stop bits to determine if it could proceed to the next bundle or if it needed to wait, regardless of the processor's width (number of execution units). This was a significant step toward making VLIW-like architectures more practical and scalable.

Software Prefetch: Mitigating Memory Latency

To tackle the issue of non-deterministic memory latency, EPIC incorporated software prefetch instructions.

Software Prefetch Instruction: An instruction explicitly inserted into the instruction stream by the compiler to request data to be loaded into the cache before it is actually needed by a subsequent instruction. This aims to reduce memory latency by proactively fetching data, increasing the likelihood of a cache hit when the data is eventually accessed.

Compilers, with their understanding of program data access patterns, could insert prefetch instructions to bring data into the cache hierarchy in advance of its use. This proactive approach aimed to hide memory latency and improve overall performance by minimizing stalls caused by waiting for data to be fetched from memory. Furthermore, prefetch instructions in EPIC could also provide hints about the temporal locality of data, indicating how long the data was likely to be needed, allowing the cache system to manage data more efficiently.

Speculative Load and Check Load: Handling Data and Control Dependencies

EPIC introduced speculative load and check load instructions to further enhance Instruction-Level Parallelism by addressing both control and data dependencies.

Speculative Load Instruction: An instruction that initiates a memory load operation before it is definitively known whether the loaded data will actually be needed or if the load is even safe to execute. This allows execution to proceed speculatively, potentially overlapping memory access latency with other operations.

Check Load Instruction: An instruction used in conjunction with speculative loads to verify whether a speculative load was valid. It checks if a speculative load might have been affected by a subsequent store operation (data dependency violation). If a violation is detected, the check load instruction triggers a recovery mechanism, typically a reload of the data.

Speculative Load: In traditional execution, the processor would wait until it was certain that a load instruction was necessary and safe to execute. Speculative loads allowed the processor to initiate loads before resolving control dependencies (e.g., whether a branch will be taken and the load instruction will be reached) or data dependencies (e.g., whether another instruction might modify the data before it is used). This speculative execution could hide memory latency and keep execution units busy.

Check Load: Because speculative loads could potentially load data that might be overwritten or not ultimately needed, EPIC included "check load" instructions. These instructions acted as validation steps. After a speculative load, a check load would verify if the loaded data was still valid. For example, it would check if a store operation had occurred to the same memory location after the speculative load but before the data was used. If the check failed, it indicated that the speculative load was invalid, and the data needed to be reloaded. This mechanism ensured correctness while still reaping the benefits of speculative execution.

EPIC's Arsenal for Increased Instruction-Level Parallelism (ILP)

Beyond addressing the limitations of VLIW, EPIC incorporated a "grab-bag" of architectural concepts aimed at maximizing Instruction-Level Parallelism (ILP). These techniques were designed to reduce control flow overhead, manage exceptions more efficiently, and improve register utilization.

Predicated Execution: Reducing Branch Penalties

Predicated Execution: A technique that eliminates or reduces the impact of branch instructions by conditionally executing instructions based on the value of a "predicate" register. Instead of branching around a block of code, predicated execution allows both paths of a conditional statement to be fetched and potentially executed. The results of the instructions are then selectively committed based on the predicate, effectively "killing" the results from the path that should not have been taken.

Branch instructions, which alter the control flow of a program, can introduce pipeline stalls and limit ILP. EPIC employed predicated execution to mitigate these branch penalties. Instead of using branches to conditionally execute code, EPIC used predicate registers. A predicate register would hold a boolean value (true or false) representing the condition of a branch. Instructions could then be predicated – meaning their execution would be conditional on the value of a predicate register. If the predicate was true, the instruction would execute normally; if false, its results would be discarded ("killed"). This allowed the processor to execute instructions from both paths of a conditional branch speculatively, reducing the performance impact of branches and increasing ILP.

Delayed Exceptions: Enabling Speculation Past Potential Errors

Delayed Exceptions: A mechanism that allows speculative execution to proceed past instructions that might potentially cause exceptions (e.g., division by zero, memory access violations). Instead of immediately halting execution upon encountering a potential exception, the exception is flagged and delayed until it is certain that the instruction's result is actually needed. If the speculative execution path is not taken, the exception is effectively ignored.

Exceptions, which indicate errors or unusual conditions during program execution, can also disrupt the flow of execution and limit speculation. EPIC used delayed exceptions to allow speculative execution to proceed even past instructions that might potentially cause exceptions. A "not a thing" bit in general-purpose registers was used to flag potential exceptions. If an instruction might cause an exception, the "not a thing" bit would be set instead of immediately triggering the exception. The actual exception would be delayed until it was determined that the result of the potentially exception-causing instruction was actually needed. If the speculative path was not taken, the delayed exception would be ignored, allowing for more aggressive speculation.

Very Large Architectural Register Files: Minimizing Register Renaming

Register Renaming: A hardware technique used in superscalar processors to eliminate false data dependencies between instructions that use the same registers but are actually independent. Register renaming dynamically maps architectural registers (registers visible to the programmer) to a larger pool of physical registers within the processor, allowing instructions to execute out-of-order without being stalled by register conflicts.

Register renaming is a complex hardware mechanism used in superscalar architectures to overcome limitations imposed by the finite number of architectural registers. EPIC, in contrast, opted for very large architectural register files. By providing a large number of registers directly visible to the programmer, EPIC aimed to reduce the need for register renaming. Compilers could allocate registers more freely, minimizing register conflicts and simplifying instruction scheduling, contributing to higher ILP and simpler hardware design.

Multi-Way Branch Instructions: Improving Branch Prediction

Branch Prediction: A hardware technique used to predict the outcome of branch instructions (whether they will be taken or not taken) before they are actually executed. Accurate branch prediction is crucial for maintaining pipeline efficiency in modern processors, as mispredictions can lead to pipeline flushes and performance penalties.

Branch prediction is critical for performance in pipelined processors. EPIC introduced multi-way branch instructions to improve branch prediction accuracy. These instructions allowed a single bundle to encode multiple possible branch targets. This gave the branch prediction hardware more information to make more informed predictions, especially in scenarios with complex control flow, potentially improving prediction accuracy and reducing branch misprediction penalties.

Rotating Register Files: Enabling Software Pipelining

The Itanium architecture, the flagship implementation of EPIC, further incorporated rotating register files, a feature particularly beneficial for software pipelining.

Rotating Register Files: A register file organization that automatically renames registers in a loop during software pipelining. This eliminates the need for manual register renaming by the compiler, simplifying the process of creating efficient software pipelines for loop execution.

Software Pipelining: A compiler optimization technique used to improve the performance of loops by overlapping the execution of different iterations of the loop. It aims to fill the processor pipeline by starting new iterations before previous iterations have fully completed, maximizing throughput.

Software pipelining is a compiler optimization technique to enhance loop performance by overlapping iterations. However, it often requires complex register management, including register renaming. Rotating register files in Itanium automated this register renaming process. As a loop iterates, the register file "rotates," effectively assigning new physical registers to variables in each iteration. This simplified software pipelining and made it more efficient, contributing to improved loop performance, which is crucial for many applications.

Other Research and Development

While Itanium was the most prominent implementation of EPIC, it's important to note that EPIC concepts were also explored in other research and development projects. The Wikipedia article mentions a few key initiatives:

• IMPACT Project (University of Illinois at Urbana–Champaign): Led by Wen-mei Hwu, the IMPACT project was a significant academic research effort that contributed greatly to the understanding and development of EPIC architectures. It was a source of influential research on compiler techniques and architectural principles relevant to EPIC.
• PlayDoh Architecture (HP Labs): PlayDoh was another major research project within HP Labs that explored EPIC concepts independently of the Itanium development. It represented a different approach to EPIC design and furthered the understanding of the paradigm.
• Gelato (Open Source Community): Gelato was an open-source community focused on developing high-performance compilers for Linux applications running on Itanium servers. It was a collaborative effort between academic and commercial researchers aimed at optimizing software for EPIC architectures and fostering wider adoption.

These projects demonstrate that EPIC was not solely confined to the HP-Intel partnership but represented a broader research direction in computer architecture.

Conclusion: EPIC - A Vision Ahead of Its Time?

Explicitly Parallel Instruction Computing (EPIC) represented a significant departure from traditional microprocessor design paradigms. By shifting the complexity of parallel instruction scheduling to the compiler, EPIC aimed to achieve scalable performance while simplifying hardware and enhancing Instruction-Level Parallelism. Its innovations, including bundles, stop bits, speculative execution, predicated execution, and large register files, were all geared towards realizing this vision.

While EPIC's most prominent implementation, the Itanium architecture, did not achieve widespread mainstream success in the desktop and server markets as initially anticipated, the ideas and concepts behind EPIC were undeniably innovative and ahead of their time. The challenges of compiler complexity, the evolving landscape of computing demands, and perhaps the inherent difficulty in fundamentally shifting the hardware-software balance in processor design contributed to its limited mainstream adoption.

However, EPIC's legacy is not one of failure but rather of pioneering exploration. It pushed the boundaries of computer architecture, explored the potential of compiler-directed parallelism, and contributed valuable insights into the challenges and opportunities of exploiting Instruction-Level Parallelism. In the context of "lost computer innovations," EPIC stands as a testament to the ambitious ideas that, while not fully realized in their original form, have nonetheless enriched the field of computer architecture and continue to inform the ongoing quest for ever more powerful and efficient computing systems. The principles of compiler-directed parallelism and explicit instruction-level parallelism continue to be relevant in modern computing, even as architectures have evolved in different directions.